Khi chiến tranh bùng nổ, ông tham gia một cách năng nổ, làm sĩ quan tham mưu của Tướng Erich Hoepner chỉ huy Sư đoàn 6 Thiết giáp trong các chiến dịch tại Ba Lan và Pháp. Chính trên chiến trường Nga mà Stauffenberg cảm thấy vỡ mộng. Sự tàn bạo của lực lượng SS ở Liên Xô cũng như lệnh của Hitler bắn bỏ chính ủy Bolshevik đã khiến cho Stauffenberg mở mắt mà nhận ra con người thật của Hitler. Do tình cờ, ông gặp hai người chủ chốt trong nhóm âm mưu chống Hitler: Tướng Henning von Tresckow, Tham mưu trưởng cụm Tập đoàn quân Trung tâm và sĩ quan dưới quyền ông này Fabian von Schlabrendorff, rồi hoạt động một cách cách tích cực trong nhóm.

Nhưng Stauffenberg vẫn còn là một sĩ quan cấp thấp và thấy các thống chế quá hoang mang – hoặc quá hèn nhát – nên không thể làm gì để loại trừ Hitler hoặc chấm dứt việc tàn sát người Do Thái, người Nga và tù binh. Thảm họa xảy ra một cách không cần thiết ở Stalingrad, dẫn đến việc tập đoàn quân số 6 của Đức đầu hàng, cũng làm cho ông chán ngán. Tháng 2/1943, ông xin chuyển ra chiến trường và được cử làm sĩ quan hành quân cho sư đoàn thiết giáp số 10 ở Tunisia.

Ngày 7 tháng 4, chiếc xe chở ông cán phải mìn – có nguồn nói xe của ông bị một máy bay Đồng Minh tấn công – và ông bị thương nặng. Ông mất con mắt trái, bàn tay phải, hai ngón tay bên kia, và thêm những vết thương ở tai trái và đầu gối. Trong nhiều tuần có vẻ như nếu ông sống sót thì cũng bị mù hẳn, nhưng ông được chữa trị và hồi phục. Người ta có thể nghĩ như ai khác hẳn đã muốn xin ra khỏi quân đội và từ bỏ nhóm âm mưu. Trong khi đang hồi phục, ông có thời gian để suy nghĩ và đi đến kết luận là, dù cho bị thương tật, ông phải thực hiện một nhiệm vụ thiêng liêng.

Ông nói với vợ, Nữ Bá tước Nina, mẹ của bốn đứa con của ông: "Anh nghĩ bây giờ anh phải làm gì đó để cứu nước Đức. Sĩ quan tham mưu quân đội như anh phải nhận lãnh một phần trách nhiệm."